package com.zhj.algorithm.sort;

import java.util.Arrays;

/**
 * @PackageName:com.zhj.algorithm.sort
 * @ClassName:MergeSort
 * @auter: 朱慧杰
 * @date:2020/8/9 0009 18:04
 **/
public class MergeSort {

    // 归并排序
    public static void main(String[] args) {
        int[] arr = new int[]{4,3,5,8,7,6,1,0,2};
        System.out.println(Arrays.toString(arr));
        mergeSort(arr, 0, arr.length-1);
        System.out.println(Arrays.toString(arr));
    }

    public static void mergeSort(int[] arr,int low,int high) {
        int middle = (high + low) / 2;
        if (low < high) {
            // 处理左边
            mergeSort(arr, low, middle);
            // 处理右边
            mergeSort(arr, middle+1, high);
            // 归并
            merge(arr, low, middle, high);
        }
    }

    public static void merge(int[] arr,int low,int middle,int high) {
        // 归并后的零时数组
        int[] temp = new int[high-low+1];
        // 记录第一个数组需要遍历的下标
        int i = low;
        // 记录第二个数组需要遍历的下标
        int j = middle+1;
        //记录零时数组下标
        int index = 0;
        // 遍历两个数组取出最小的数字，放入零时数组中
        while (i <= middle && j <= high) {
            if (arr[i] <= arr[j]) {
                temp[index] = arr[i];
                i++;
            } else {
                temp[index] = arr[j];
                j++;
            }
            index++;
        }
        // 处理多余数据
        while (j <= high) {
            temp[index] = arr[j];
            j++;
            index++;
        }
        while (i <= middle) {
            temp[index] = arr[i];
            i++;
            index++;
        }
        // 零时数组重新存入原来的数组
        for (int k = 0; k < temp.length; k++) {
            arr[k+low] = temp[k];
        }
    }

}
